package com.kevin.Code.OfferReviewVersion2;

/**
 * @author Vinlee Xiao
 * @Classname NumberofProvinces
 * @Description Leetcode 547. 省份数量 同剑指 OfferII 116 中等难度
 * @Date 2022/1/21 21:04
 * @Version 1.0
 */
public class NumberofProvinces {

    /**
     * @param isConnected
     * @return
     */
    public int findCircleNum(int[][] isConnected) {

        int row = isConnected.length;
        int col = isConnected[0].length;
        //省份的最大数量
        int proviceNum = isConnected.length;
        //利用并查集来查找省份的数量 parent记录共同祖先
        int[] parent = new int[isConnected.length];

        //初始化parent[i]数组
        for (int i = 0; i < row; i++) {
            parent[i] = i;
        }

        for (int i = 0; i < row; i++) {
            for (int j = i + 1; j < col; j++) {
                if (isConnected[i][j] == 1 && !findUnion(parent, i, j)) {
                    proviceNum--;
                }
            }
        }

        return proviceNum;

    }

    /**
     * 返回false表示不属于同一个子集
     * true表示属于同一个子集
     *
     * @param parent
     * @param i
     * @param j
     * @return
     */
    private boolean findUnion(int[] parent, int i, int j) {

        int rootIndex1 = findCommonParent(parent, i);
        int rootIndex2 = findCommonParent(parent, j);
        //合并并查集
        if (rootIndex1 != rootIndex2) {
            parent[rootIndex1] = rootIndex2;
            return false;
        }
        return true;
    }


    /**
     * 核心怎么理解这个算法?
     *
     * @param parent
     * @param i
     * @return
     */
    private int findCommonParent(int[] parent, int i) {
        //如果当前顶点i的根节点和其自身初始节点相同，则找到其父节点的根节点
        if (i != parent[i]) {
            return findCommonParent(parent, parent[i]);
        }
        return parent[i];
    }

    /**
     * @param isConnected
     * @return
     */
    public int findCircleNum1(int[][] isConnected) {

        int provinceNum = 0;
        boolean[] visited = new boolean[isConnected.length];
        for (int i = 0; i < isConnected.length; i++) {
            if (!visited[i]) {
                dfs(isConnected, i, visited);
                provinceNum++;
            }
        }

        return provinceNum;
    }

    /**
     * @param isConnnected
     * @param vertex
     * @param visited
     */
    private void dfs(int[][] isConnnected, int vertex, boolean[] visited) {

        visited[vertex] = true;
        for (int i = 0; i < isConnnected.length; i++) {
            if (!visited[i] && isConnnected[vertex][i] == 1) {
                dfs(isConnnected, i, visited);
            }
        }
    }


}
